package SortMethod;


import SortHelper.SortHelper;

import java.util.Random;

//这次写的是老师教的方法，比我那个暴力解决还是好一些的
public class QuickSort01 {

    private QuickSort01(){}

    public static <E extends Comparable<E>> void sort(E[] arr){
        sort(arr,0,arr.length - 1);
    }

    private static <E extends Comparable<E>> void sort(E[] arr,int l,int r){
        if (l >= r)return; //必须把等于条件也算进去，不然会报错
        int p = partition(arr,l,r);
        sort(arr,l,p-1);
        sort(arr,p+1,r);
    }

    private static <E extends Comparable<E>> int partition(E[] arr,int l,int r){
        //加了个取数组中随机数为开头，这样可以很好应付本来就有序的数组，但平常的数组会变慢
        //其实暴力点可以直接取数组的中间那个数，但如果遇到十分特殊的数组就寄了
        Random rd = new Random();
        int rnd = l + rd.nextInt(r - l + 1);
        SortHelper.swap(arr,rnd,l);
        int j = l;
        for (int i = l + 1; i <= r; i++) {
            if (arr[i].compareTo(arr[l]) < 0){
                j++;
                SortHelper.swap(arr,i,j);
            }
        }
        SortHelper.swap(arr,l,j);
        return j;
    }

    //自己测试的代码
//    public static void main(String[] args) {
//        Integer[] arr = {5,8,7,9,6,1,2};
//        int p = partition(arr,0,arr.length - 1);
//        System.out.println(p);
//        sort(arr);
//        for (int n: arr){
//            System.out.printf("%d ",n);
//        }
//    }
}
